Task-based execution models depart from bulk-synchronized processing (BSP) models in that they express the exact amount of parallelism among tasks in a program. Instead of a sequence of doall-parallel tasks separated by barriers, the program represents the exact set of tasks that need to complete before the execution of a particular task to be semantically correct. The main advantages of task-based execution models are that they expose as much parallelism as possible and avoid BSP synchronizations, which may not scale well with the number of concurrent and irregular tasks, and when there is hardware induced load imbalance, such as in the context of Near Threshold Computing (NTC), where parameter-induced variation are estimated to cause core speeds to diverge by as much as four times.
The parallelizing compiler's job is to form tasks from a sequential specification of the program, and to compute dependences that relate these tasks to each other. Some compilers, e.g., R-Stream™, both tasks and their dependences can be represented in a compact form: a small set of polyhedrons is sufficient to represent the full set of tasks and their dependences, even when the number of such tasks and dependences depends upon runtime-defined parameters. This is enabled by the use of the polyhedral model, and the task and the dependence representation is compact compared with many other models in which each individual task is represented separately, as well as their dependences. Such a representation generally does not permit the representation of programs whose number of tasks would depend upon runtime parameters. However, a limitation that comes with the power of the polyhedral representation is the computational complexity of some of the algorithms for manipulating the polyhedrons that represent the program. Of interest in this section is polyhedral projection, which suffers from combinatorial explosion.
When a loop in a program to be compiled is tiled, the dependences between instances of statements in the tiled loop may need to be computed for execution using an event driven tasks (EDT) computing system. Some methods first form dependence relationships among pairs of tiled references. The dependence domain is expressed in the Cartesian product of the tiled iteration domains of the source and destination (polyhedral) statements. The task dependences are generally obtained by projecting out the inter-tile dimensions in both source and destination iteration spaces.
Unfortunately, this method does not scale well, because even though it applies well on the rational relaxation of the dependence domain, it relies on applying a projection operation on a high-dimensional polyhedron (the dependence domain). Projection is currently one of the least tractable operations on rational polyhedrons. For all practical purposes, the main parameter in the computation time of a polyhedral projection is the number of dimensions of the polyhedron. Unfortunately, the state of the art technique to compute task dependences relies on the formation and projection of a high-dimensional polyhedron. As a result, this technique can become impractical as it results in compilation timeouts.